package com.flashshe.ds.list
{
	

	public class SinglyLinkedList extends AbstractList
	{
		private var head:SinglyLinkedListElement;		
		private var count:int = 0;
		
		
		public function SinglyLinkedList()
		{
			super();
		}
		
		public override function get size():int
		{
			return count;
		}
		
		public override function clear():void
		{
			head = null;
			count = 0;
		}				
		
		public override function add(v:Object):void
		{			
			if (head == null)
			{
				head = new SinglyLinkedListElement(v);
			}
			else
			{
				var finger:SinglyLinkedListElement = head;
				while(finger.nextElement)
				{
					finger = finger.nextElement;
				}
				
				finger.nextElement = new SinglyLinkedListElement(v);
			}
			
			count += 1;
		}
		
		public override function addAt(index:uint, v:Object):void
		{			
			if (index > size)
			{
				throw new RangeError("提供的索引超出了范围");
			}			
			
			if (head == null)
			{
				add(v);
				return;
			}
						
			
			// 列表中至少有一个元素			
			
			//插入列表头部
			if (0 == index)
			{
				head = new SinglyLinkedListElement(v, head);
				count += 1;
				return;
			}
			
			if (index == size)
			{
				add(v);
				return;
			}
			
			// 列表中至少有两个元素并且不会插入头部
			var i:int = 0;			
			var finger:SinglyLinkedListElement = head;
			var pre:SinglyLinkedListElement = null;
			
			while(finger.nextElement)
			{
				pre = finger;
				finger = finger.nextElement;
				i += 1;
				if (i == index)
				{
					break;
				}				
			}
			
			pre.nextElement = new SinglyLinkedListElement(v, finger);
									
			count += 1;
		}
				
		public override function getValueAt(index:uint):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}
			
			var finger:SinglyLinkedListElement = head;
			var i:int = 0;
			
			do 
			{
				if (i == index)
				{					
					return finger.value;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i <= index);

			return null;
		}
		
		public override function getLast():Object
		{
			return getValueAt(size-1);
		}
		
		public override function removeAt(index:uint):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}	
			var result:Object;
			
			if (index == 0)
			{
				result = head.value;
				head = head.nextElement;
				count -= 1;
				return result;
			}
			
			var i:int = 0;			
			var finger:SinglyLinkedListElement = head;
			var pre:SinglyLinkedListElement = null;
			
			while(finger.nextElement)
			{
				pre = finger;
				finger = finger.nextElement;
				i += 1;
				if (i == index)
				{
					break;
				}				
			}
			
			pre.nextElement = finger.nextElement;			
			count -= 1;
			result = finger.value;
			
			return result;
		}
		
		public override function remove():Object
		{						
			return removeAt(size-1);
		}
		
		public override function setValueAt(index:uint, v:Object):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}
			
			var i:int = 0;			
			var finger:SinglyLinkedListElement = head;
			
			do
			{
				if (i == index)
				{					
					var result:Object = finger.value;
					finger.value = v;
					return result;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i < count);			
			
			return null;
		}							
		
		public override function indexOf(v:Object, startIndex:uint=0):int
		{
			if (count == 0 || startIndex >= count)
			{
				return -1;
			}
			
			var i:int = 0;			
			var finger:SinglyLinkedListElement = head;
			
			do
			{
				if (finger.value == v && i >= startIndex)
				{					
					return i;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i < count);
			
			return -1;
		}
		
		/*public override function iterator():IIterator
		{
			return null;
		}*/
	}
}